The present invention relates to associative memories and in particular memories of the  less than  less than TRIE greater than  greater than  type (derived from the English verb  less than  less than reTRIEve greater than  greater than ).
The principle of the  less than  less than TRIE greater than  greater than  memory was proposed by R. de la Briandais and E. Fredkin et al towards the end of the 1950s (see E. Fredkin et al.:  less than  less than Trie Memory greater than  greater than , Communications of the ACM, Vol. 3, No. 9, September 1960, pages 490-499). It consists in cutting up the bit strings to be recognised into successive slices of a fixed length (of K bits) and integrating them in a two-dimensional table T. Each row of the table constitutes a register of 2K elementary cells. A register (R) is assigned to each slice of the string and a cell in the register is associated with the value (V), ranging between 0 and 2Kxe2x88x921 of this slice. The contents (C=T[R,V]) of the cell determined in this manner represent either the register allocated to the subsequent slice (or pointer) or an end of analysis reference (or  less than  less than status greater than  greater than ) if the analysis of the string must end on this slice.
The register allocated to the first slice of the string, which is also the point of entry to the table, is also referred to as the gate. The data to be analysed in the form of bit strings, i.e. to be compared with the contents of the TRIE memory, will also be referred to as routes hereafter. The term path will be used to denote the succession of concatenated cells in the table associated with a route. Each register of the table will be said to be of the order of ixe2x89xa70 if it is attributed to the (i+1)-th slice of one or more stored routes. The gate register will therefore be in the order of 0. The TRIE memory associates with each of the registers in the order of ixe2x89xa70 a unique sequence of iK bits corresponding to the iK first bits of each route whose path in the table passes via a cell of the register in question.
The following example will provide an illustration of how data is stored in a TRIE memory in the specific case where K=4. The value of each slice is represented by a digit in hexadecimal numbering (0,1, . . . E,F) and each of the registers contains 24=16 cells.
Let us assume that the routes to be recognised are those commencing with the codes 45A4, 45AB, 67AB, 788A and 788BD, to which the statuses S0, S1, S2, S3 and S0 have been allocated respectively (a same status may be shared by several routes). By using the row index for the register R and the column index for the value V of the slices and by taking the register R0=0 as the gate, the table of the TRIE memory will appear as illustrated in FIG. 1, the underlined data being the statuses. The codes 45A4, 45AB, 67AB, 788A and 788BD are represented respectively in the table of FIG. 1 by the paths:
T[0,4]xe2x86x92T[1,5]xe2x86x92T[2,A]xe2x86x92T[3,4];
T[0,4]xe2x86x92T[1,5]xe2x86x92T[2,A]xe2x86x92T[3,B];
T[0,6]xe2x86x92T[4,7]xe2x86x92T[5,A]xe2x86x92T[6,B];
T[0,7]xe2x86x92T[7,8]xe2x86x92T[8,8]xe2x86x92T[9,A];
T[0,7]xe2x86x92T[7,8]xe2x86x92T[8,8]xe2x86x92T[9,B]xe2x86x92T[10,D].
From this example, it may be seen that all the codes starting with a common part of iK bits are represented by a common initial path in the memory leading to the register of order i with which the sequence formed by these iK bits is associated.
If we consider a route to be analysed, cut up into a series of binary slices of values Vi where 0xe2x89xa6ixe2x89xa6N and {Ri} is the series of registers associated with the values Vi, where R0 still denotes the gate register, the analysis algorithm implemented may be that illustrated in FIG. 2.
On initialisation 1 of this algorithm, the analysis rank i is set to 0 and the gate register R0 is selected as the register R. In each iteration of rank i, the contents C of the cell T[R,Vi], denoted by the (i+1)-th slice Vi of the route in the register of order i selected, is read at step 2. If this cell contains a continue analysis pointer, which is indicated at test 3 by the value 1 for a bit FP(C) stored in the cell, the register of order i+1 denoted by this pointer Ptr(C) is selected as the register R for the next iteration at step 4 and the rank i is incremented. If test 3 reveals a cell which does not contain a pointer (FP(C)=0), the status Ref(C) read in the cell concerned is returned at step 5 as a result of looking up the table.
This algorithm enables routes containing any number of slices to be analysed. A same table may be used for several types of analysis, managing data on the basis of different gates. Furthermore, it enables the analysis time of the data to be controlled: analysing a number N of slices of K bits will require at most N times the duration of one iteration.
The algorithm of FIG. 2 may be implemented very rapidly by a hardware component managing accesses to the table memory. In particular, it will enable high-performance routers to be set up for packet-switched telecommunications networks. The header of the packets is analysed by the component on the fly and the status associated with a route designates, for example, an output port of the router to which the packets bearing a destination address conforming to this route must be routed.
Such a router may be a multi-protocol router. This being the case, the different sections of the header are analysed from different gates. For example, a first analysis of a header field (or several) indicating the protocol used and/or the version of this protocol may be analysed from a first gate. This first analysis will provide a reference which, although corresponding to a logical end of the analysis, may be embodied in the TRIE memory by a continue analysis pointer denoting another gate register to be used for analysing the rest of the header. The reference in question may also trigger time delays or skips by a given number of bits in the header being analysed in order to be able to choose which portion of the header should be analysed next. In practice, a certain number of analyses are generally run in succession in order to trigger the operations required by the protocols supported, depending on the content of the headers. One of these analyses will relate to the destination address needed to complete the routing function strictly speaking.
A router of the type outlined above is described in U.S. Pat. No. 5,781,431. On the subject of using a TRIE memory in routers, reference may be made to the article  less than  less than Putting Routing Tables in Silicon greater than  greater than  by T. B. Pei et al., IEEE Network Magazine, January 1992, pages 42-50.
The fact of being able to string together several elementary analyses and insert programmable skips between them lends a high degree of flexibility to the method, particularly when processing encapsulated protocols of the ISO model in several layers. Analysing slices of the header on the fly as they arrive also enhances speed.
However, in a certain number of situations, it is useful to be able to move backward in the header in order to examine certain fields in an order other than that in which they arrived. This will often allow better optimisation of the memory size required. It is also a feature required by certain protocols, such as the RSVP reservation protocol or multicast protocols.
An object of the present invention is to further improve the processing flexibility offered by TRIE memories, especially in routing applications.
Accordingly, the invention proposes a method of associating forwarding references with data packets by means of a TRIE memory, whereby different gate registers of the TRIE memory analyse in succession different portions of a header of each packet containing protocol data. When a packet arrives, its header is stored in a buffer memory and a first portion of the stored header is analysed. Each analysis of a header portion of a packet produces either the forwarding reference associated with the packet or an intermediate reference containing a first code, which makes it possible to locate at an arbitrary location of the buffer memory a subsequent portion to be analysed, and a second code, which makes it possible to locate at an arbitrary location of the TRIE memory a gate register from which said subsequent portion should be analysed. Having analysed the first portion of a stored header, the subsequent portions thereof are analysed in accordance with the first and second codes contained in the intermediate references produced in succession until the forwarding reference is obtained.
Consequently, the contents of the TRIE memory no longer represent only the reference associated with the packet headers as such. They also incorporate a programme consisting of the string of elementary analyses to be performed, depending on the different configurations taken into account by the memory. These strings are entirely programmable insofar as the user can define, arbitrarily and at each step of the process, which portion of the header must be examined and from which register of the TRIE memory.
Another aspect of the present invention relates to a packet processing device such as a packet router having a circuit for analysing the header of the packets received using an associative memory of the TRIE type which operates in accordance with the method outlined above.